package 算法模板;

/**
 * 二分查找算法只能对有序的数据有效
 * 写法 1： while(left <= right) 这种写法可以认为我们在循环体
 * 内部直接查找元素，不断找到符合条件的元素，最后一个值是最符合条件的元素
 * right = mid - 1; left = m + 1;
 * <p>
 * 写法 2：while(left < right) 这种写法表示在循环体内部排除元素，最后一个元素就是结果
 * right = mid;  left=mid+1或者...
 */
public class 二分查找 {

    //常规的二分查找，如果是无序的，先排序， Arrays.sort();
    public int binarySearch(int[] nums, int key) {
        //1，定义左右边界
        int left = 0, right = nums.length - 1;
        //2，设置循环停止条件(因为right = nums.length - 1,所以[left,right]
        while (left <= right) {
            //3，取得中间值的下标
            int m = left + (right - left) / 2;
            //4，设置要查值的条件
            if (nums[m] == key) {
                return m;
            } else if (nums[m] > key) { //中间值大于key，右边界减半
                right = m - 1;
            } else { //否则左边界减半
                left = m + 1;
            }
        }
        return -1;
    }
}
